Mac Mania 5

home *** CD-ROM | disk | FTP | other *** search

/ Mac Mania 5 / MacMania 5.toast / / Tools&Utilities / TimGA 1.1 / More Documentation / Help (TimGA) next >

Wrap

Text File | 1996-08-17 | 18.9 KB | 385 lines | [ttro/ttxt]

_______________________________________________________________ TimGA — A freeware Mac application Version 1.1 (August 1996) By Timo Eloranta Copyright © 1995-96 Brown Eyes Software All rights reserved. Internet e-mail: timo.eloranta@ac.com _______________________________________________________________ If you're not familiar with genetic algorithms, I suggest you read "The Hitch-Hiker's Guide to Evolutionary Computation" (edited by Joerg Heitkoetter and David Beasley), which is the FAQ (a list of Frequently Asked Questions) for the comp.ai.genetic newsgroup. It is available from http://www.cis.ohio-state.edu/hypertext/faq/usenet/ai-faq/genetic/top.html _______________________________________________________________ Please read the "Read Me (TimGA)" file if you haven't already. This document — "Help (TimGA)" — contains additional info about the main window, the menu items and the dialogs of TimGA. Okay, here we go... The Main Window The main window of TimGA has the following fields: • Name: = The name of the currently open graph. • Nodes: = The quantity of nodes in the current graph. • Edges: = The quantity of edges in the current graph. • Grid Size: = The size of the drawing grid. This can be changed with the "General..." command in the "Settings" menu. The default grid size is 40x40. The minimum size is 2x2 (try it!) and the maximum is 70x70. • Pop. Size: = The size of the population used by the genetic algorithm. This too can be changed from the General Settings. • Cur. Generation: = The number of the current generation. This is 0 until the iteration is started. • Running Time: = The time (minutes:seconds) that the genetic algorithm has used for processing the current graph. Note that this does not equal the time from the start of the iteration, because some of the time is spent outside the genetic algorithm (e.g. the time spent updating the best ever drawing, which is visible on the right side of the main window...). • Least Crossings: = The smallest quantity of edge crossings in any of the drawings in our current population (yes, the population in TimGA consists of drawings). • Avg. Crossings: = The average quantity of edge crossings in our current population. • Iter. State: = The current state of the iteration. The possible states are: "No graph" (when no graph is loaded), "Start me up!" (when all is ready for the iteration to begin), "Running" (when iterating in the foreground), "Running (bg)" (when iterating in the background), "Paused" (when the user has halted the iteration manually) and "Done" (when the iteration has ended because of one of the termination conditions). • Fitness: = The fitness of the best drawing found so far. Two values are given. The first value is the number of edge crossings in our best drawing. The second value is the value given by our fitness function (see the "Evaluation..." dialog in the "Settings" menu for details). • Generation: = The number of the generation when the best drawing was found. • No Change (Gen.): = Generations since the best drawing was found. • No Change (Time): = Time spent iterating since the best drawing was found. On the right side of the main window you can always see the best drawing found so far. If you haven't opened a graph, all you see is the drawing grid. The Menus • Apple menu: About TimGA... = Every decent Mac app needs a cool About box. Is this cool enough? • File: Open Graph... = With this command you can load one of the graph files. Note that only one graph can be open at any single time. • File: Rnd New Graph... = With this command you can create a random new graph to be drawn. The quantity of nodes and edges must be entered. Note that TimGA only supports so called simple graphs, which have no self loops and no more than one edge between any two nodes. TimGA checks the validity of the values you enter, so you don't really need to worry... • File: Close Graph = With this command you can close the current graph. Note that you don't actually need to use this command before opening another graph because opening another graph will automatically (and without any warnings...) close the old graph. You'll mainly need this command to get access to the General Settings dialog, which is not available if any graph is open. • File: Quit = Quits the program. No questions asked. • Edit: Copy = New functionality in TimGA 1.1 !! With this command you can copy a drawing to clipboard. You can then paste the picture to any graphics or word processing program. This allows you to save and print the drawings produced with TimGA. Before copying the picture you might want to switch to b&w with the new Switch to B&W command and/or hide the grid with the Hide Grid command (both in Drawing menu). To change the size of the drawing use the Increase/Decrease Square Size commands. Note also, that the size of the grid (e.g. 10x10 or 40x40) affects your possibilities of changing the square size, but you can only change the grid size (from the General settings dialog) _before_ opening a graph... • Edit: Cut, Paste, Clear, Select All... = The ordinary stuff. Can only be used in dialogs with edit fields. • Iteration: Start/Continue = When you have an open graph, you can start the iteration with this command. If you have manually paused the iteration you can use this same menu item to continue the iteration. If the iteration has stopped because of one of the termination conditions, and you'd like to still continue the iteration further, you should first remove the termination condition that caused the halting. This is done with the Termination... dialog. • Iteration: Pause = This command pauses the iteration temporarily. You can continue the iteration with the Continue command if you want. (These instructions are getting awfully boring. I hope it's not a sign of a boring program...) • Iteration: Reinitialize = When a new graph is opened, the drawings (note that the program processes simultaneously as many drawings as the population has — even as you only see the best one on the screen!) are initialized by scattering their nodes randomly around the drawing grid. This operation can be repeated with this command. You should use this command before starting another test run with the same graph. • Settings: General... = This is the infamous General Settings menu item. And why is it not available? Oh well, here's the reason ones more: the General Settings are only available when no graph is open! If you want to change these settings, you should first close your current graph with the Close Graph command in the File menu... Now then, here's what this well protected dialog offers: • Speed = The minimum time (in ticks) between updating the information on the main screen. The default is 20 which equals 1/3 of a second (60 ticks = 1 second). So, by default the information on the screen is updated roughly 3 times per second. But here's the catch: the iteration is never interrupted in the middle of a generation and if processing one generation takes longer than the time set here (for example 20 ticks) — and believe me, with slow machines & large graphs it does — then the update interval becomes longer than the time set here. • Population = The number of drawings processed simultaneously by the program. If you're familiar with genetic algorithms, you'll know that the default value of 8 is pathetically small. The main reason for this is speed. If you have no problems with speed (this should be true if you have a PowerMac and are testing the app on smallish graphs...) go ahead and increase the population size. On the other hand, if you have a slowish Mac but would still like to try the bigger graphs, you can try decreasing the population size below the default. • Grid Size = The size of the drawing grid can be adjusted here. This setting affects the appearance of the drawings (for example the size of the nodes) but also the overall performance of the program. Why? Well, the grid should be big enough to give the nodes plenty of possible locations, but on the other hand many of the operations of the program work faster with a smaller grid... The default size (40x40) is the result of many test runs and should work well with most graphs. • Settings: Selection... = Selection is one of the stages of the genetic algorithm. If you don't know what you're doing, I suggest you stick to the default values. • Elitism = Elitism means that the best drawing of the population is always selected to the next generation. The performance of the program is VERY likely to suffer, if you turn this off. • Linear Normalization: Minimum • Linear Normalization: Step = The selection method used by TimGA is called linear normalization. This is a method described by Lawrence Davis in "Handbook of Genetic Algorithms" [1991]. The individuals of the population (drawings in this case) are sorted by their fitness. The best individual is then given a certain new score — in TimGA's case this is 100. The second best individual gets a score which is the maximum score (100) minus a so called "step value". The third best gets a score which is the maximum minus two times the step value and so on. But no individual gets a score worse than some fixed minimum score! So, if we'd for example have 8 individuals, a step value of 20 and a minimum value of 15, our "selection array" would be 100, 80, 60, 40, 20, 15, 15 and 15. The actual selection is done with these normalized fitness values. Every individual's probability of getting selected is proportional to its normalized fitness value. The best individuals are likely to get multiple selections and the worst individuals are most likely to be thrown away. The size of the population always stays the same. In TimGA the minimum score is 20 by default. Changing this will affect the so called "selection pressure", but that's too long a story to be told here! The step is by default calculated automagically with the formula: Step = (100 - Minimum) / (0.5 * Population Size) Note that this formula is by yours truly — not by Mr. Davis. • Settings: Recombination... = During every generation a part of the population is tampered with two "genetic operators": crossover and mutation (Sounds like genetics, doesn't it...). Crossover uses two individuals to create two new ones which have features from both of their "parents". Mutation makes a random change to a single individual. • Crossover Probability = With this slider you can set the probability of an individual being taken to be a part in a crossover operation. If you are familiar with genetic algorithms, you're probably surprised that the default probability is set to just 5 %. The reason for this is that I wasn't really able to create a crossover operator which would have joined two drawings of the same graph in a useful and efficient way. I tried two different approaches but the test runs showed that neither of them was really worth the processing time that they took. I left them both in TimGA though because a GA is hardly a GA without crossover, but the sad truth is that the performance of TimGA won't suffer much (if at all) even if you set the crossover probability to 0. • Mutation Probability = With this slider you can set the probability of an individual being mutated with one of the 16 different mutation operators that TimGA has in its "tool chest"... I've completed literally thousands of systematic test runs to optimize this and other parameters. I've set the default for mutation probability to 45 %, but the optimal value could be anything between 30 and 50 % depending on the graph and the size of the population and... • Settings: Evaluation... = The evaluation might be the most important phase in a GA — at least it eats most of the processing time! This is the part of the GA which should be able to measure the quality of individuals. In TimGA this is where we define how "niceness" of the drawings is measured. • Edge Crossings = By default TimGA always prefers a drawing with minimal edge crossings. The (much) more complex fitness function is only used for sorting drawings with equal quantity of crossings. If you uncheck this checkbox, the fitness function is used for all comparisons. (If you want to totally ignore the edge crossings, you should also set the correct multiplier in the fitness function to zero.) • Fitness Function = This is the function which measures the quality of the drawings! The program is trying to maximize this function. Min. Node Dist. Sum is calculated by adding up the distances from every node to their closest other node. We want this sum to as big as possible, so that the nodes would not get too close to each other. Edge Length Deviation is calculated by measuring the lengths of the edges and by then compairing the lengths to the shortest edge found. Again, a sum is calculated, but this time our goal is to minimize this sum. This part of the function supports the idea of uniform edge lengths — and also effectively shortens the longest edges. Min. Node Distance is the shortest distance between any two nodes in the drawing. In the third part of the fitness function, we divide the Edge Length Deviation with this value. This is done to balance the first two parts of the function (we want the edges to get shorter, but not too short...). The fourth part of the function rewards for spreading the nodes evenly around the drawing grid. And finally, the fifth part punishes for edge crossings. So, there you have it. My fitness function is not too elegant, but it produces fairly good results (IMHO). And by changing the default multipliers & dividers you can do your own experimenting. • Settings: Termination... = With this dialog you can set one or more termination conditions for the iteration. The iteration halts if any of the conditions is met. If you set no termination conditions, the iteration will continue until you "manually" halt the iteration with the Pause command. • Generations = You can set a limit to the total number of generations and/or the number of generations without any progress. • Time (Seconds) = You can set a limit to the iteration time (in seconds) and/or the time without finding a new best drawing. • Edge Crossings = If you check this checkbox the iteration will stop as soon as TimGA finds a drawing that has no edge crossings. • Drawing: Hide/Show Drawing = Hides/shows the best drawing by changing the size of the main window. The same effect is achieved by clicking the window's zoom box. • Drawing: Hide/Show Grid = Hides/shows the drawing grid. If you can't see the grid in the first place (except for the bright green frame), please try the "Brighten Grid" command. • Drawing: Hide/Show Edges = Hides/shows the edges of the drawing. Personally I find this command useful for checking out how evenly the nodes have spread. • Drawing: Hide/Show Nodes = Hides/shows the nodes of the drawing. Just another feature... • Drawing: Brighten/Darken Grid = I added this command because I noticed that the default grid colour was too dark (invisible actually...) on some monitors — even as its just right on my old and trusty monitor. Try it once to see the difference! • Drawing: Switch to B&W/Color = New functionality in TimGA 1.1 !! You can now switch between color and b&w modes. Personally I prefer the black and white mode when copying drawings to clipboard to be printed with some other application. • Drawing: Increase Square Size = New functionality in TimGA 1.1 !! With this command you can increase the size of the grid squares, which naturally also increases the size of the nodes. Changing the square size only affects the visual appearance of the graph - i.e. it doesn't affect the iteration process in any way. • Drawing: Decrease Square Size = New functionality in TimGA 1.1 !! With this command you can decrease the size of the grid squares, which... (see above) • Drawing: Set Square Size... = New functionality in TimGA 1.1 !! This command opens a small dialog box where you can directly change the size of the grid squares. Illegal values are rejected and if you're lucky, you might even get a sensible error message... <grin> _______________________________________________________________ Did you really read all of this? Wow!